#ifndef _DECOMP_H
#define _DECOMP_H
#include <iostream>
#include <vector>
#include <map>
#include <string>

#include "globals.h"
#include "bitops.h"
#include "Charnode.h"

using namespace std;

template <class TYPE>
class Decompressor
{
	Charnode<TYPE> *huffmanTreeRoot;
	string outputFilename;
	string compressedFilename;
	int numChars;

private:
	inline int readCount(ibstream &ibs);

	void constructTree(Charnode<TYPE> * &, int n, ibstream &ibs);

	void preorder(Charnode<TYPE> *node);

public:
	Decompressor(){}
	Decompressor(string cname, string oname);

	~Decompressor();

	void decompress();
	
	void delNode(Charnode<TYPE> *);
};


template <class TYPE>
Decompressor<TYPE>::Decompressor(string cname, string oname)
{
	outputFilename = oname;
	compressedFilename = cname;
}

template <class TYPE>
void Decompressor<TYPE>::delNode(Charnode<TYPE> * node)
{
	if(node == NULL)
		return ;

	if(node->GetLeft() != NULL)
		delNode(node->GetLeft());
	if(node->GetRight() != NULL)
		delNode(node->GetRight());

	delete node;
}

template <class TYPE>
Decompressor<TYPE>::~Decompressor()
{
	LOG(__func__)
	//delNode(huffmanTreeRoot);
	huffmanTreeRoot = NULL;
}


template < class TYPE >
int Decompressor<TYPE>::readCount(ibstream & ibs)
{
	int count = 0; 
	ibs.readbits(BITS_PER_INT, count);
	return count;
}


template <class TYPE>
void Decompressor<TYPE>::preorder(Charnode<TYPE> *node)
{
	if(node == NULL)
	{
		return;
	}

	cout << endl << node->GetChar();
	preorder(node->GetLeft());
	preorder(node->GetRight());
}


template <class TYPE> 
void Decompressor<TYPE>::constructTree(Charnode<TYPE> * &node, int n, ibstream &ibs)
{
	if(n == 0)
		return;

	if(node != NULL && node->GetLeft() != NULL && node->GetRight() != NULL)
		return;
	

	int bitread;
	ibs.readbits(1, bitread);
	if(bitread == 1)
	{
		ibs.readbits(BITS_PER_WORD, bitread);
		node = new Charnode<TYPE>((char)bitread);
		n--;
	}
	else
	{
		node = new Charnode<TYPE>('\0');
		Charnode<TYPE> *leftnode = node->GetLeft();
		Charnode<TYPE> *rightnode = node->GetRight();
		constructTree(leftnode, n, ibs);
		constructTree(rightnode, n, ibs);

		node->SetLeft(leftnode);
		node->SetRight(rightnode);
	}
}



template <class TYPE>
void Decompressor<TYPE>::decompress()
{
	// Read and build the tree
	/* 1) Read the first 8bits that represents the count of bits in the tree
	 * 2) (Reading the tree contents) 0 indicates an internal node and when a 1	
	 *    is encountered it's a leaf and the next 8 bits represent that char.
	 * 3) Thus read all the chars into a list and construct the huffman tree (Bottom Up) 
	 * 4)Use the tree and decompress the file.
	 */

	//Step 1

	vector<Charnode<TYPE> *> allchars;

	ibstream compressedFile(compressedFilename.c_str());
	obstream outputFile(outputFilename.c_str());

	int n = readCount(compressedFile);
	LOG("Huffman Tree Size read = "<< n)

	//Step 2

	huffmanTreeRoot = NULL; //new Charnode<TYPE>('\0');
	constructTree(huffmanTreeRoot, n, compressedFile);
	//preorder(huffmanTreeRoot);


	//Step 4
	int i = readCount(compressedFile);
	Charnode<TYPE> *traverser = huffmanTreeRoot;
	while(i)
	{
		int bitread;
		compressedFile.readbits(1, bitread);

		//cout << "Read bit = " << bitread;
		traverser = (bitread) ? traverser->GetRight() : traverser->GetLeft() ;

		//cout << "--> " << traverser->GetChar() << endl;
		if(traverser->GetLeft()==NULL && traverser->GetRight()==NULL)
		{
			outputFile.writebits(BITS_PER_WORD, traverser->GetChar());
			//cout << "Leaf = " << traverser->GetChar() << endl;

			traverser = huffmanTreeRoot;			
		}
		--i;
	}
	outputFile.close();
	compressedFile.close();
}




#endif
